//我们对 0 到 255 之间的整数进行采样，并将结果存储在数组 count 中：count[k] 就是整数 k 的采样个数。
//
// 我们以 浮点数 数组的形式，分别返回样本的最小值、最大值、平均值、中位数和众数。其中，众数是保证唯一的。 
//
// 我们先来回顾一下中位数的知识： 
//
// 
// 如果样本中的元素有序，并且元素数量为奇数时，中位数为最中间的那个元素； 
// 如果样本中的元素有序，并且元素数量为偶数时，中位数为中间的两个元素的平均值。 
// 
//
// 
//
// 示例 1： 
//
// 输入：count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
//,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
//,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
//,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
//,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
//,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
//,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
//输出：[1.00000,3.00000,2.37500,2.50000,3.00000]
// 
//
// 示例 2： 
//
// 输入：count = [0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
//,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
//,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
//,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
//,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
//,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
//,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
//输出：[1.00000,4.00000,2.18182,2.00000,1.00000]
// 
//
// 
//
// 提示： 
//
// 
// count.length == 256 
// 1 <= sum(count) <= 10^9 
// 计数表示的众数是唯一的 
// 答案与真实值误差在 10^-5 以内就会被视为正确答案 
// 
// Related Topics 数学 双指针 
// 👍 20 👎 0


package cn.db117.leetcode.solution10;

import java.util.Arrays;

/**
 * 1093.大样本统计.statistics-from-a-large-sample
 *
 * @author db117
 * @since 2021-06-21 11:17:12
 **/

public class Solution_1093 {
    public static void main(String[] args) {
        Solution solution = new Solution_1093().new Solution();
        System.out.println(Arrays.toString(solution.sampleStats(new int[]{
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3510, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6718, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 27870, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 35, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 26256, 0, 0, 0, 0, 9586565, 0, 0, 0, 0, 0, 0, 0, 2333, 0, 0, 0, 0
        })));

        //0.0,255.0,128.64187,131.0,175.0
        // 32.0,251.0,242.40435,243.0,243.0
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double[] sampleStats(int[] count) {
            // 最小值、最大值、平均值、中位数和众数
            int min = 256;
            int max = 0;
            long sum = 0, numCount = 0;
            double mid = 0;
            int mode = 0, maxNum = 0;

            // 除了中位数都可以一次遍历解决
            for (int i = 0, countLength = count.length; i < countLength; i++) {
                int n = count[i];
                numCount += n;// 总个数
                sum += (long) n * i;// 和

                // 最小值
                if (min == 256 && n != 0) {
                    min = i;
                }

                if (n != 0) {
                    // 最大值
                    max = Math.max(max, i);
                }

                if (n > maxNum) {
                    // 众数
                    maxNum = n;
                    mode = i;
                }
            }

            // 上面已经统计出数字的数量
            int index = 0;
            for (int i = 0; i < count.length; i++) {
                int n = count[i];

                if (n == 0) {
                    // 跳过0
                    continue;
                }
                index += n;

                if (index > numCount / 2) {
                    // 中位数肯定是当前数字
                    mid = i;
                    break;
                } else if (index == numCount / 2) {
                    // 下一个一个数字
                    int next = i + 1;
                    while (next < count.length && count[next] == 0) {
                        next++;
                    }
                    // 中位数有可能是下一个数字
                    if (numCount % 2 == 0) {
                        // 偶数个数字
                        mid = (double) (i + next) / 2;
                    } else {
                        mid = next;
                    }
                    break;
                }

                if (numCount == 1) {
                    // 只有一个数字
                    mid = i;
                    break;
                }
            }


            return new double[]{min, max, (double) sum / numCount, mid, mode};
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}